#include<iostream>
#include<cstring>
using namespace std;
#define int long long
const int N = 1e5 + 10;
int n;
int f[N];
int add[N];
int a[N];
int fun(int x)
{
	if (a[x] > a[x + 1] && a[x] > a[x - 1])return 0;
	int z = max(a[x - 1], a[x + 1]);
	return abs(z - a[x]) + 1;
	//return min(abs(a[x] - a[x + 1]), abs(a[x] - a[x - 1])) + 1;
}
signed main()
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}
		for (int i = 2; i <= n - 1; i++) {
			add[i] = fun(i);
			f[i] = 0;
		}
		if (n & 1) {
			int ans = 0;
			for (int i = 2; i < n; i += 2) {
				ans += add[i];
			}
			cout << ans << endl;
		}
		else {
			f[1] = 0;
			f[2] = add[2];
			f[3] = add[3];
			for (int i = 4; i <= n - 1; i++) {
				if (i & 1)f[i] = min(f[i - 2], f[i - 3]) + add[i];
				else f[i] = f[i - 2] + add[i];
			}
			cout << min(f[n - 1], f[n - 2]) << endl;
		}
	}
	return 0;
}